#!usr/bin/env python  
# -*- coding:utf-8 -*-
""" 
@author:robot
@file: code_04.py 
@version:
@time: 2023/08/19 
"""
import sys


def linear_find_max_subarray(array):
    left = 0
    right = 0
    i = left
    j = right
    max_sum = -sys.maxsize - 1
    sum_now = 0
    while j < len(array):
        sum_now += array[j]
        if sum_now > max_sum:
            max_sum = sum_now
            left = i
            right = j
        if sum_now < 0:
            sum_now = 0
            i = j + 1
        j += 1
    return array[left:right + 1], max_sum


array = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]
sub_array, max_sum1 = linear_find_max_subarray(array)
print("the max sub array is {0} and sum is {1}".format(sub_array, max_sum1))

